package solution;

import solution.util.ListNode;

/**
 * <a href="https://www.nowcoder.com/practice/152bc6c5b14149e49bf5d8c46f53152b?tpId=202&&tqId=38714&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC5 链表的插入排序</a>
 *
 * @author or2
 * @Description 使用插入排序对链表进行排序。
 * @create 2021年09月14日 时间: 15:34
 */
public class InsertionSortList {
    /**
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode insertionSortList(ListNode head) {
//        检测输入
        if (head == null) {
            return null;
        }
//        辅助头结点
        ListNode headAux = new ListNode(0);
        headAux.next = head;
//        未排序链表的头结点
        ListNode p = headAux;

//        进行插入排序
        while (p.next != null) {
//            遍历已排序的链表. 寻找插入位置
            ListNode q = headAux;
            while (p.next.val > q.next.val) {
                q = q.next;
            }
//            新插入的元素比有序链表中所有元素都大
            if (q == p) {
                p = p.next;
                continue;
            }
//            插入到合适位置
            ListNode pNext = p.next.next;
//            头插法
            p.next.next = q.next;
            q.next = p.next;
            p.next = pNext;
        }

        return headAux.next;
    }
}
